package org.basis.algorithm.lru;

import lombok.Data;

import java.util.HashMap;
import java.util.Map;

/**
 * 手写Lru练习
 *
 * @author Mr_wenpan@163.com 2022/02/21 11:15
 */
public class MyLru01 {

    /**
     * 具体存放数据的map
     */
    private Map<String, Node> map = new HashMap<>();
    /**
     * 记录访问频次的链表头节点
     */
    private Node head;
    /**
     * 记录访问频次的链表尾节点
     */
    private Node tail;
    /**
     * 内存限制
     */
    private int limit;

    public MyLru01(int limit) {
        if (limit <= 0) {
            throw new RuntimeException("Note limit can not be less than 0.");
        }
        this.limit = limit;
    }

    public String get(String key) {
        // 默认不允许空值key
        if (key == null) {
            return null;
        }
        Node node = map.get(key);
        // 没有get到元素，直接返回空，不需要调整链表
        if (node == null) {
            return null;
        }
        // 本身就是尾巴节点，不动
        if (node == tail) {
            return node.value;
        }
        // 如果当前节点是头节点
        if (node == head) {
            // 释放头节点
            head = node.next;
            head.pre = null;
            node.next = null;
            // 放到链表尾部
            tail.next = node;
            node.pre = tail;
            tail = node;
            return node.value;
        }

        // 先将节点从链表上断开，然后重新加入到链表尾部
        Node next = node.next;
        Node pre = node.pre;

        next.pre = pre;
        pre.next = next;

        tail.next = node;
        node.pre = tail;
        tail = node;

        return node.value;
    }

    public String put(String key, String value) {
        if (key == null || value == null) {
            throw new RuntimeException("Note key not be null.");
        }

        // 先检查map中是否存在
        Node node = map.get(key);
        // 如果存在就覆盖，然后移动链表节点到链表尾部
        if (node != null) {
            Node next = node.next;
            Node pre = node.pre;
            pre.next = next;
            next.pre = pre;
            tail.next = node;
            node.pre = tail;
            tail = node;
        } else {
            // 如果超出容量限制，则先释放头节点
            if (map.size() >= limit) {
                Node next = head.next;
                // head.next == null 则说明链表上只有一个节点
                if (next != null) {
                    // help gc
                    next.pre = null;
                    head.next = null;
                } else {
                    tail = null;
                }
                head = next;
                map.remove(key);
            }

            // 元素添加到集合
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            // 加入链表尾部
            if (head == null) {
                head = newNode;
                tail = newNode;
            } else {
                tail.next = newNode;
                newNode.pre = tail;
                tail = newNode;
            }
        }

        return value;
    }

    /**
     * 链表节点
     */
    @Data
    static class Node {
        String key;
        String value;
        Node next;
        Node pre;

        public Node(String key, String value) {
            this.key = key;
            this.value = value;
        }
    }

}
